{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 两个字符串str1和str2，返回这两个字符串的最长公共子序列的长度，\n",
    "# 子序列是指原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串\n",
    "def max_str(str1,str2):\n",
    "    m,n=len(str1),len(str2)\n",
    "    dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "\n",
    "    for i in range(1,m+1):\n",
    "        for j in range(1,n+1):\n",
    "            if str1[i-1]==str2[j-1]:\n",
    "                dp[i][j]=dp[i-1][j-1]+1\n",
    "            else:\n",
    "                dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n",
    "\n",
    "    return dp[m][n]\n",
    "\n",
    "str1='abcde'\n",
    "str2='acex'\n",
    "\n",
    "max_str(str1,str2)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
